{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### leetcode daily log"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[(100, 1), (37, 10)]\n",
      "{100: 0, 37: 1}\n",
      "1\n",
      "[(16, 7), (34, 7), (43, 7), (18, 9)]\n",
      "{16: 0, 34: 1, 43: 2, 18: 3}\n",
      "2\n"
     ]
    }
   ],
   "source": [
    "#3551.数位和排序需要的最小交换次数\n",
    "class Solution:\n",
    "    def minSwaps(self, nums: list[int]) -> int:\n",
    "\n",
    "        # 计算数位和\n",
    "        def get_sum(num):\n",
    "            if num<10:\n",
    "                return num\n",
    "            return get_sum(num//10)+num%10\n",
    "        sort_nums=[(num,get_sum(num)) for num in nums]\n",
    "        # Sort by digit sum first, then by original value\n",
    "        sort_nums.sort(key=lambda x: (x[1], x[0]))\n",
    "        print(sort_nums)\n",
    "        # Create mapping from number to target index\n",
    "        index_map={v[0]:i for i,v in enumerate(sort_nums)}\n",
    "        print(index_map)\n",
    "        # Count swaps needed\n",
    "        swaps_count = 0\n",
    "        for i,v in enumerate(nums):\n",
    "            target_index=0\n",
    "            while (target_index:=index_map[v])!=i:\n",
    "                v,nums[target_index] = nums[target_index], v\n",
    "                swaps_count += 1\n",
    "        return swaps_count\n",
    "\n",
    "\n",
    "\n",
    "nums=[37,100]\n",
    "print(Solution().minSwaps(nums))\n",
    "# 输出：1\n",
    "print(Solution().minSwaps([18,43,34,16]))\n",
    "# 输出：2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3120"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "570+30+360+30+780+480+870"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "base",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.12.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
